#include <iostream>

#define NUM 4
#define TOTAL 10

int max(int a, int b)
{
    return a > b ? a : b;
}
int main(int argc, char** argv)
{
    int weight[NUM + 1] = {0, 5, 4, 6, 3};
    int value[NUM + 1] = {0, 10, 40, 30, 50};

    int dp[NUM + 1][TOTAL + 1] = {{0}};

    for (int i = 1; i <= NUM; i++)
    {
        for (int j = 0; j <= TOTAL; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= weight[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
            //std::cout << "dp[" << i << "][" << j << "]="<< dp[i][j] << std::endl;
        }
    }
    std::cout << dp[NUM][TOTAL] << std::endl;

    int sdp[TOTAL + 1] = {0}; 
    for (int i = 1; i <= NUM; i++)
    {
        for (int j = TOTAL; j >= weight[i]; j--)
        {
            std::cout << "dp[" << j << "]" << sdp[j] << std::endl;
            sdp[j] = max(sdp[j], sdp[j - weight[i]] + value[i]);
        }
    }
    std::cout << sdp[TOTAL] << std::endl;
    /*
       for i:=1 to n do
       for j:=totv downto v[i] do
       f[j]:=max(f[j],f[j-v[i]]+p[i]）;
       writeln(f[totv]);
       */
    return 0;
}
